home *** CD-ROM | disk | FTP | other *** search
/ CU Amiga Super CD-ROM 19 / CU Amiga Magazine's Super CD-ROM 19 (1998)(EMAP Images)(GB)[!][issue 1998-02].iso / CUCD / Programming / LEDA / incl / LEDA.020+881 / impl / dlist.h < prev    next >
Encoding:
C/C++ Source or Header  |  1994-08-05  |  6.8 KB  |  248 lines
  1. /*******************************************************************************
  2. +
  3. +  LEDA  3.1c
  4. +
  5. +
  6. +  dlist.h
  7. +
  8. +
  9. +  Copyright (c) 1994  by  Max-Planck-Institut fuer Informatik
  10. +  Im Stadtwald, 6600 Saarbruecken, FRG     
  11. +  All rights reserved.
  12. + 
  13. *******************************************************************************/
  14.  
  15.  
  16.  
  17. #ifndef LEDA_DLIST_H
  18. #define LEDA_DLIST_H
  19.  
  20. //------------------------------------------------------------------------------
  21. //  doubly linked lists
  22. //------------------------------------------------------------------------------
  23.  
  24. #include <LEDA/basic.h>
  25.  
  26. //------------------------------------------------------------------------------
  27. // some declarations
  28. //------------------------------------------------------------------------------
  29.  
  30. class dlist; 
  31. class dlink;
  32.  
  33. typedef dlink* list_item;
  34.  
  35. //------------------------------------------------------------------------------
  36. // class dlink (list items)
  37. //------------------------------------------------------------------------------
  38.  
  39. class dlink {
  40.  
  41.   dlink* succ;
  42.   dlink* pred;
  43.   GenPtr e;
  44.  
  45.   dlink(GenPtr a, dlink* pre, dlink* suc)
  46.   { 
  47.     e = a;
  48.     succ = suc;
  49.     pred = pre;
  50.   }
  51.  
  52.   LEDA_MEMORY(dlink)
  53.  
  54.  
  55.   friend class dlist;
  56.   FRIEND_INLINE dlink* succ_item(dlink* p);
  57.   FRIEND_INLINE dlink* pred_item(dlink* p);
  58.  
  59.  
  60.   //space: 3 words = 12 bytes
  61. };
  62.  
  63.  
  64. inline dlink* succ_item(dlink* p) { return p->succ; }
  65. inline dlink* pred_item(dlink* p) { return p->pred; }
  66.  
  67.  
  68. //------------------------------------------------------------------------------
  69. // dlist: base class for all doubly linked lists
  70. //------------------------------------------------------------------------------
  71.  
  72. class dlist {
  73.  
  74.    dlink* h;                     //head
  75.    dlink* t;                     //tail
  76.    dlink* iterator;              //iterator
  77.    int count;                    //length of list
  78.  
  79. //space: 4 words + virtual =  5 words = 20 bytes
  80.  
  81. virtual int  cmp(GenPtr x, GenPtr y)  const { return compare(x,y); }
  82. virtual void read_el(GenPtr&,istream&) {}
  83. virtual void print_el(GenPtr& x,ostream& out) const { Print(int(x),out); }
  84. virtual void clear_el(GenPtr&) const {}
  85. virtual void copy_el(GenPtr&)  const {}
  86. virtual int  int_type() const { return 0; }
  87.  
  88. void quick_sort(list_item*,list_item*);
  89. void quick_sort(list_item*,list_item*,CMP_PTR);
  90. void int_quick_sort(list_item*,list_item*);
  91.  
  92. void insertion_sort(dlink**,dlink**,dlink**);
  93. void insertion_sort(dlink**,dlink**,dlink**,CMP_PTR);
  94. void int_insertion_sort(dlink**,dlink**,dlink**);
  95.  
  96. void recompute_length() const;
  97.  
  98. public:
  99.  
  100. // access operations
  101.  
  102.    int  length() const { if (count < 0) recompute_length(); return count; }
  103.    int  size()   const { return length(); }
  104.    bool empty()  const { return h==nil; }
  105.  
  106.    dlink* first()               const { return h; }
  107.    dlink* first_item()          const { return h; }
  108.    dlink* last()                const { return t; }
  109.    dlink* last_item()           const { return t; }
  110.    dlink* next_item(dlink* p)   const { return p->succ; }
  111.    dlink* succ(dlink* l)        const { return l->succ; }
  112.    dlink* pred(dlink* l)        const { return l->pred; }
  113.    dlink* cyclic_succ(dlink*)   const;
  114.    dlink* cyclic_pred(dlink*)   const;
  115.    dlink* succ(dlink* l, int i) const; 
  116.    dlink* pred(dlink* l, int i) const;
  117.    dlink* get_item(int = 0)     const; 
  118.  
  119.    dlink* max(CMP_PTR) const;
  120.    dlink* min(CMP_PTR) const;
  121.    dlink* search(GenPtr) const;
  122.  
  123.    int    rank(GenPtr) const;
  124.  
  125.    GenPtr contents(dlink* l) const { return l->e; }
  126.    GenPtr head()             const { return h ? h->e : 0;}
  127.    GenPtr tail()             const { return t ? t->e : 0;}
  128.  
  129.  
  130. // update operations
  131.  
  132. protected:
  133.  
  134.    dlink* insert(GenPtr a, dlink* l, int dir=0);
  135.  
  136.    dlink* push(GenPtr a)   
  137.    { count++;
  138.      if (h) h = h->pred = new dlink(a,0,h); 
  139.      else   h = t =  new dlink(a,0,0);
  140.      return h;
  141.     }
  142.    
  143.    dlink* append(GenPtr a)
  144.    { count++;
  145.      if (t) t = t->succ = new dlink(a,t,0);
  146.      else   t = h = new dlink(a,0,0);
  147.      return t; 
  148.     } 
  149.    
  150.    void   assign(dlink* l, GenPtr a) { copy_el(a); l->e = a; }
  151.  
  152.  
  153. public:
  154.  
  155.    GenPtr del(dlink* loc);
  156.    GenPtr pop();
  157.    GenPtr Pop();
  158.  
  159.    void   conc(dlist&,int dir=0);
  160.    void   split(list_item,dlist&,dlist&,int dir=0);
  161.    void   apply(APP_PTR);
  162.    void   sort(CMP_PTR);
  163.    void   bucket_sort(int,int,ORD_PTR);
  164.    void   permute();
  165.    void   clear();
  166.  
  167. // iteration
  168.  
  169.    void   set_iterator(dlink* p)   const { (dlink*&)iterator = p; }
  170.    void   start_iteration()        const { set_iterator(h); }
  171.    void   Start_iteration()        const { set_iterator(t); }
  172.    void   move_to_succ()           const { set_iterator(iterator->succ); }
  173.    void   move_to_pred()           const { set_iterator(iterator->pred); }
  174.    dlink* read_iterator(GenPtr& x) const { if (iterator) x = iterator->e; 
  175.                                            return iterator; }
  176.    dlink* read_ptr_iterator(GenPtr& x) 
  177.                                    const { if (iterator) x = iterator->e; 
  178.                                            return iterator; }
  179.  
  180.    GenPtr loop_to_succ(GenPtr& x) const { return x = list_item(x)->succ; }
  181.    GenPtr loop_to_pred(GenPtr& x) const { return x = list_item(x)->pred; }
  182.  
  183.  
  184. //  old iteration stuff
  185.  
  186.    void  reset()               const { set_iterator(nil); }
  187.    void  init_iterator()       const { set_iterator(nil); }
  188.  
  189.    dlink* get_iterator()       const { return iterator; }
  190.    dlink* move_iterator(int=0) const;
  191.  
  192.    bool   current_element(GenPtr&) const;
  193.    bool   next_element(GenPtr&)    const;
  194.    bool   prev_element(GenPtr&)    const;
  195.  
  196.  
  197. // operators
  198.  
  199.    GenPtr&   entry(dlink* l)            { return l->e; }
  200.    GenPtr    inf(dlink* l)        const { return l->e; }
  201.    GenPtr&   operator[](dlink* l)       { return l->e; }
  202.    GenPtr    operator[](dlink* l) const { return l->e; }
  203.  
  204.    dlist& operator=(const dlist&); 
  205.    dlist  operator+(const dlist&); 
  206.  
  207.  
  208.    void print(ostream&,string, char)       const;    
  209.    void print(ostream& out,char space=' ') const { print(out,"",space);  }
  210.    void print(string s, char space=' ')    const { print(cout,s,space);  }
  211.    void print(char space=' ')              const { print(cout,"",space); }   
  212.  
  213.  
  214.    void read(istream&,string, char);  
  215.  
  216.    void read(istream& in,char delim) { read(in,"",delim); }
  217.    void read(istream& in)            { read(in,"",EOF); }
  218.  
  219.    void read(string s, char delim)  { read(cin,s,delim); }   
  220.    void read(string s)              { read(cin,s,'\n'); }   
  221.  
  222.    void read(char delim)  { read(cin,"",delim);}  
  223.    void read()            { read(cin,"",'\n');}  
  224.  
  225.  
  226. // constructors & destructors
  227.  
  228.    dlist();    
  229.    dlist(GenPtr a);
  230.    dlist(const dlist&);
  231.  
  232.    virtual ~dlist()  { clear(); }
  233.  
  234.    int space()  const { return sizeof(dlist) + count * sizeof(dlink); }
  235. };
  236.  
  237.  
  238.  
  239. // default I/O and cmp functions
  240.  
  241. inline void Print(const dlist& L,ostream& out) { L.print(out); }
  242.  
  243. inline void Read(dlist& L, istream& in) { L.read(in); }
  244.  
  245. inline int compare(const dlist&,const dlist&) { return 0; }
  246.  
  247. #endif
  248.